package stack.easy;

import java.util.Stack;

/**
 * 1. 问题描述、
 *      给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。
 *      注意：如果对空文本输入退格字符，文本继续为空。
 *
 * 2. 算法分析
 *      你可以用 O(N) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？
 *
 * 3， 代码实现
 */
@SuppressWarnings("all")
public class 比较含退格的字符串 {
    public static void main(String[] args) {
        String s = "ada";
        Stack<Character> stack = new Stack<>();
        boolean empty = stack.empty();
        System.out.println(empty);
        char ch = '#';

    }

    public static boolean backspaceCompare(String S, String T) {
        Stack<Character> stackS = new Stack<>();
        Stack<Character> stackT = new Stack<>();
        for(char ch : S.toCharArray()) {
            if(ch == '#') {
                if(stackS.isEmpty()){
                    // 栈空
                    continue;
                } else{
                    stackS.pop();
                }
            } else {
                stackS.add(ch);
            }
        }
        for(char ch : T.toCharArray()) {
            if(ch == '#') {
                if(stackT.isEmpty()){
                    // 栈空
                    continue;
                } else{
                    stackT.pop();
                }
            } else {
                stackT.add(ch);
            }
        }
        if(stackS.size() != stackT.size()) {return false;}
        for(int i = 0; i < stackS.size(); i++) {
            if(stackS.get(i) != stackT.get(i)) {
                return false;
            }
        }
        return true;
    }
}
